package com.itheima.algorithm.datastructure;

/**
 * @Author: zhangshao
 * @Since: 2024/4/30 16:23
 */
public class Leetcode234 {

	public static boolean isPalindrome(ListNode head){

		/**
		 *   1  2  2  1
		 *   反转后逐值比较
		 *
		 */
		// 步骤1：找中间点
		ListNode middle = middle(head);

		// 步骤2：中间点后半个链表反转
		ListNode newHead = reverse(middle);
		// 步骤3：反转后链表与原链表逐一比较
		while (newHead!=null){
			if(newHead.value !=head.value){
				return false;
			}
			newHead = newHead.next;
			head = head.next;
		}
		return true;



	}

	private static ListNode reverse(ListNode o1){
		ListNode n1 = null;
		while (o1!=null){
			ListNode o2 =o1.next;
			//旧链表头指向新链表
			o1.next = n1;
			n1 = o1;
			o1=o2;
		}
		return n1;
	}

	/**
	 *
	 * @param head
	 * @return
	 */
	private static ListNode middle(ListNode head){
		// 快慢指针法

		ListNode p1 = head;//慢指针
		ListNode p2 = head;//快指针
		while(p2 !=null &&p2.next!=null){
			p1 = p1.next;
			p2 = p2.next;
			p2 = p2.next;
		}
		return p1;

	}

	public static void main(String[] args) {
		ListNode head1 = ListNode.of(1, 2, 2, 1);
		ListNode head2 = ListNode.of(1, 2, 3, 2, 1);

		System.out.println(isPalindrome(head1));
		System.out.println(isPalindrome(head2));
	}
}
